#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution1 {
private:
    unordered_map<int, int> memo;

public:
    int minDays(int n) {
        if (n <= 1) {
            return n;
        }
        if (memo.count(n)) {
            return memo[n];
        }
        return memo[n] = min(n % 2 + 1 + minDays(n / 2), n % 3 + 1 + minDays(n / 3));
    }
};

bool check(int num)
{
    if (num <= 1) return false;
    bool res = true;
    for (int i = 2; i <= num / i; ++i)
    {
        if (num % i == 0)
        {
            res = false;
            break;
        }
    }
    return res;
}

class Solution2
{
public:
    void solve()
    {
        int n; cin >> n;
        vector<int> nums(n + 1); int sum = 0;
        for (int i = 1; i <= n; ++i)
        {
            cin >> nums[i];
            sum += nums[i];
        }
        if (sum % 2)
        {
            cout << "false" << endl;
            return 0;
        }

        vector<bool> dp(sum / 2);
        dp[0] = true;
        for (int i = 1; i <= n; ++i)
            for (int j = sum / 2; j >= nums[i]; --j)
            {
                dp[j] = dp[j] || dp[j - nums[i]];
            }

        if (dp[sum / 2])
            cout << "true" << endl;
        else
            cout << "false" << endl;

    }
};

class Solution3 {
public:
    using pii = pair<int, int>;
    int dx[4] = { 1,-1,0,0 };
    int dy[4] = { 0,0,1,-1 };

    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size(); int n = grid[0].size();
        queue<pii> q; int fcnt = 0;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == 2) q.push({ i,j });
                else if (grid[i][j] == 1) ++fcnt;
            }

        int res = -1;
        while (!q.empty())
        {
            int sz = q.size(); ++res;
            while (sz--)
            {
                auto [a, b] = q.front();
                q.pop();
                for (int k = 0; k < 4; ++k)
                {
                    int x = a + dx[k]; int y = b + dy[k];
                    if (x >= 0 && y >= 0 && x < m && y < n && grid[x][y] == 1)
                    {
                        q.push({ x,y });
                        grid[x][y] = 2;
                        --fcnt;
                    }
                }
            }
        }

        if (fcnt) return -1;
        return res == -1 ? 0 : res;
    }
};


class Solution4 {
public:
    int minimumRounds(vector<int>& tasks) {
        unordered_map<int, int> mp;
        for (int x : tasks)
            ++mp[x];
        int res = 0;
        for (auto& [_, cnt] : mp)
        {
            if (cnt == 1) return -1;
            res += cnt / 3;
            if (cnt % 3)
                ++res;
        }
        return res;
    }
};

const int mod = 109;
using ll = long long;

int main()
{
    int n, m; cin >> n >> m;
    ll res = n; --m; ll a = n - 1;
    for (int i = m; i > 0; i >>= 1)
    {
        if (i & 1)
            res = (1LL * res * a) % mod;
        a = a * a % mod;
    }
    cout << res;
    return 0;
}